1019. 链表中的下一个更大节点【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 单调栈

1. 📝 题目描述

• leetcode

给定一个长度为 n 的链表 head

对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。

返回一个整数数组 answer，其中 answer[i] 是第 i 个节点( 从 1 开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0。

---

示例 1：

输入：head = [2,1,5]
输出：[5,5,0]

示例 2：

输入：head = [2,7,4,3,5]
输出：[7,0,5,5,0]

---

提示：

• 链表中节点数为 n
• 1 <= n <= 10^4
• 1 <= Node.val <= 10^9

2. 🎯 s.1 - 单调栈

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {ListNode} head
 * @return {number[]}
 */
var nextLargerNodes = function (head) {
  const vals = []
  let cur = head
  while (cur) {
    vals.push(cur.val)
    cur = cur.next
  }
  const n = vals.length
  const res = new Array(n).fill(0)
  const stack = [] // index stack
  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && vals[stack[stack.length - 1]] < vals[i]) {
      res[stack.pop()] = vals[i]
    }
    stack.push(i)
  }
  return res
}

• 时间复杂度：$O(n)$，其中 $n$ 是链表的长度
• 空间复杂度：$O(n)$，栈和结果数组的空间

算法思路：

• 先将链表转为数组，然后用单调栈求每个元素的下一个更大值
• 维护一个单调递减栈，栈中存储索引
• 当当前元素大于栈顶元素时，弹出栈顶并记录答案